import java.util.*;

public class Test {
    //前k个高频单词
    public static List<String> topKFrequent(String[] words, int k) {
        //1.统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word: words) {
            if(map.get(word) == null){
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val  + 1);//跟新value值
            }
        }

        //2.建立小根堆

        PriorityQueue<Map.Entry<String,Integer>> minHeap =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey()); //根据字母顺序建立大根堆
                }
                return o1.getValue() - o2.getValue();
            }
        });
        //需要传入比较器(比较val的值)

        //3.遍历map  调整优先级队列

        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //当前频率相同
                if(top.getValue().compareTo(entry.getValue()) == 0){
                    //字母顺序小的进来
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        //要由高到低排序
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }

        Collections.reverse(ret);//逆置
        return ret;
    }
}
